package J4_6;

import java.util.Arrays;

public class test {
    //一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
    //
    //'A' -> "1"
    //'B' -> "2"
    //...
    //'Z' -> "26"
    //要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
    //
    //"AAJF" ，将消息分组为 (1 1 10 6)
    //"KJF" ，将消息分组为 (11 10 6)
    //注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
    //
    //给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
    //
    //题目数据保证答案肯定是一个 32 位 的整数。
    public int numDecodings(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (c[0] != '0') dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            if (c[i - 1] - '0' != 0) dp[i] += dp[i - 1];
            int t =(c[i - 2] - '0') * 10 + c[i - 1] - '0';
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }

    //一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    //
    //机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    //
    //问总共有多少条不同的路径？
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }


    //一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    //
    //机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
    //
    //现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
    //
    //网格中的障碍物和空位置分别用 1 和 0 来表示。
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (obstacleGrid[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }


    //现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
    //
    //只能从架子的左上角开始拿珠宝
    //每次可以移动到右侧或下侧的相邻位置
    //到达珠宝架子的右下角时，停止拿取
    //注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
    public int jewelleryValue(int[][] frame) {
        int r = frame.length, l = frame[0].length;
        int[][] dp = new int[r + 1][l + 1];
        dp[1][1] = frame[0][0];
        for (int i = 1; i < r + 1; i++) {
            for (int j = 1; j < l + 1; j++) {
                int max = Math.max(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = max + frame[i - 1][j - 1];
            }
        }
        return dp[r][l];
    }

    //给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
    //
    //下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
    // 在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
    // 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
    public static int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 1) {
            return matrix[0][0];
        }
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = matrix[i][j];
                    continue;
                }
                int min = dp[i - 1][j];
                if (j > 0) min = Math.min(min, dp[i - 1][j - 1]);
                if (j < n - 1) min = Math.min(min, dp[i - 1][j + 1]);
                dp[i][j] = min + matrix[i][j];
            }
        }
        int ret = dp[n - 1][0];
        for (int i = 1; i < n; i++) {
            ret = Math.min(ret, dp[n - 1][i]);
        }
        return ret;
    }

    //给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    //
    //说明：每次只能向下或者向右移动一步。
    public int minPathSum(int[][] grid) {
        int r = grid.length, l = grid[0].length;
        int[][] dp = new int[r + 1][l + 1];
        for (int i = 0; i < r + 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < l + 1; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        dp[1][0] = 0;
        for (int i = 1; i < r + 1; i++) {
            for (int j = 1; j < l + 1; j++) {
                dp[i][j] = Math.min(dp[i][j - 1],dp[i - 1][j]) + grid[i - 1][j - 1];
            }
        }
        return dp[r][l];
    }

    //恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
    //
    //骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
    //
    //有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
    //
    //为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
    //
    //返回确保骑士能够拯救到公主所需的最低初始健康点数。
    //
    //注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间
    public static int calculateMinimumHP(int[][] dungeon) {
        int r = dungeon.length, l = dungeon[0].length;
        int[][] dp = new int[r + 1][l + 1];
        for (int i = 0; i < r + 1; i++) {
            dp[i][l] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < l + 1; i++) {
            dp[r][i] = Integer.MAX_VALUE;
        }
        dp[r - 1][l] = 1;
        for (int i = r - 1; i >= 0; i--) {
            for (int j = l - 1; j >= 0 ; j--) {
                int a = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = a > 0 ? a : 1;
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[][] array = {
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5}
        };
        int a = calculateMinimumHP(array);
        System.out.println(1);
    }


}
